package com.java.xiaoBao;

import java.util.Stack;

public class AcrossMiGong {

    /**
     * 寻找迷宫出路坐标
     */
    Stack<Node> acrossMiGong(){

        Stack<Node> s = new Stack<Node>();
        //指定迷宫入口
        Node start = new Node(0,18);
        s.add(start);

        int k = 0;
        // 右-->下--左-->上
        //栈不为空
        while(!s.empty()) {
            //isRight==true
            if(!start.right && start.isRight()) {
                Node nright = new Node(start.x, start.y+1);

                if(!s.contains(nright)){   //防止在走不通的情况下， 产生环路现象！ 下同
                    nright.left = true;
                    start.right = true;
                    s.add(nright);
                    start = nright;
                }else {
                    start.right = true;
                }
                //isDown==true
            }else if(!start.down && start.isDown()) {
                Node ndown = new Node(start.x+1, start.y);
                if(!s.contains(ndown)) {
                    start.down = true;
                    ndown.up = true;
                    s.add(ndown);
                    start = ndown;
                }else {
                    start.down = true;
                }
                //isLeft==true
            }else if(!start.left && start.isLeft()) {
                Node nleft = new Node(start.x, start.y-1);
                if(!s.contains(nleft)) {
                    start.left = true;
                    nleft.right = true;
                    s.add(nleft);
                    start = nleft;
                }else {
                    start.left = true;
                }
                //isUp==true
            }else if(!start.up && start.isUp()) {
                Node nup = new Node(start.x-1, start.y);
                if(!s.contains(nup)) {
                    start.up = true;
                    nup.down = true;
                    s.add(nup);
                    start = nup;
                }else {
                    start.up = true;
                }

            }else if(!s.empty()) {
                //弹出数据
                s.pop();
                if(s.empty()) {
                    System.out.println("没有找到路径，栈为空");
                    return null;
                }
                //返回栈顶
                start = s.peek();
            }
            if(isSucceed(start)) {
                return s;
            }
        }
        return null;
    }


    /**
     * 判断是否成功
     */
    boolean isSucceed(Node node){

        // 指定出口路径，最后迷宫找到即为成功
        if((node.x == 15) && (node.y == 19)) {
            return true;
        }
        return false;
    }


}
